package com.mdnote.algorithm;

import java.util.Arrays;


/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/10
 * @description 克鲁斯卡尔算法
 */
public class KruskalAlgorithm {

    private static final int INF = 65535;

    public static void main(String[] args) {

        KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm();

        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weights = {
                {  0,  12, INF, INF, INF,  16,  14},
                { 12,   0,  10,   9, INF,   7, INF},
                {INF,  10,   0,   3,   5,   6, INF},
                {INF, INF,   3,   0,   4, INF, INF},
                {INF, INF,   5,   4,   0,   2,   8},
                { 16,   7,   6, INF,   2,   0,   9},
                { 14, INF, INF, INF,   8,   9,   0}
        };

        // 统计边的个数
        int edgeNum = 0;
        for (int i = 0; i < weights.length; i++) {
            for (int j = i + 1; j < weights[i].length; j++) {
                if (weights[i][j] != INF && weights[i][j] != 0) {
                    edgeNum++;
                }
            }

        }

        // 初始化边
        Edge[] edges = new Edge[edgeNum];
        int index = 0;
        for (int i = 0; i < weights.length; i++) {
            for (int j = i + 1; j < weights[i].length; j++) {
                if (weights[i][j] != INF) {
                    edges[index] = new Edge(vertex[i], vertex[j], weights[i][j]);
                    index++;
                }
            }
        }
        // 进行克鲁斯卡尔计算
        MGraph mGraph = new MGraph(vertex.length, vertex, weights, edges);
        Edge[] rets = kruskalAlgorithm.kruskal(mGraph);
        System.out.println(Arrays.toString(rets));
        for (int i = 0; i < rets.length && rets[i] != null; i ++) {
            System.out.println("从" + rets[i].start + "走到" + rets[i].end + "共" + rets[i].weight + "步");
        }
    }

    /**
     * 克鲁斯卡尔算法
     * @param mGraph 图
     * @return 结果集
     */
    private Edge[] kruskal(MGraph mGraph) {

        // 用于动态记录各个顶点的终点
        int[] ends = new int[mGraph.edgeCount];
        // 最终的边
        Edge[] rets = new Edge[mGraph.edgeCount];

        int index = 0;
        // 县排序
        sort(mGraph.edges);
        for (int i = 0; i < mGraph.edges.length; i++) {
            // 获取起点索引
            int startIndex = mGraph.getIndex(mGraph.edges[i].start);
            // 获取终点索引
            int endIndex = mGraph.getIndex(mGraph.edges[i].end);
            // 根据索引查看终点索引
            int startEndIndex = getEnd(ends, startIndex);
            int endEndIndex = getEnd(ends, endIndex);
            // 判断两个终点是否相等
            if (startEndIndex != endEndIndex) {
                // 在ends的startIndex位置上设置终点索引
                ends[startEndIndex] = endEndIndex;
                // 保存这条边
                rets[index++] = mGraph.edges[i];
            }

        }
        return rets;
    }

    /**
     * 获取终点
     * @param ends 终点记录数组
     * @param index 起点索引
     * @return 终点索引
     */
    private int getEnd(int[] ends, int index) {
        while (ends[index] != 0) {
            index = ends[index];
        }
        return index;
    }

    /**
     * 排序，冒泡
     * @param edges 数组
     */
    private void sort(Edge[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - i - 1; j++) {
                if (edges[j].weight > edges[j + 1].weight) {
                    Edge temp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = temp;
                }
            }
        }
    }


    private static class Edge {
        private char start;
        private char end;
        private int weight;

        public Edge(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "start=" + start +
                    ", end=" + end +
                    ", weight=" + weight +
                    '}';
        }
    }


    private static class MGraph {

        private int vertexCount;
        private int edgeCount;
        private char[] vertex;
        private int[][] weights;
        // 边
        private Edge[] edges;

        public MGraph(int vertexCount, char[] vertex, int[][] weights, Edge[] edges) {
            this.vertexCount = vertexCount;
            this.vertex = vertex;
            this.weights = weights;
            this.edges = edges;
            this.edgeCount = edges.length;
        }

        public void setVertex(char[] vertex) {
            this.vertex = vertex;
        }

        public void setWeights(int[][] weights) {
            this.weights = weights;
        }

        /**
         * 获取顶点的索引
         * @param c 字符
         * @return 索引
         */
        public int getIndex(char c) {
            for (int i = 0; i < vertex.length; i++) {
                if (c == vertex[i]) {
                    return i;
                }
            }
            return -1;
        }
    }
}
